package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

/**
 * https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 105 前序 中序 还原树
 * 106 后序 中序 还原树 这俩差不多
 *
 * <p>
 * see 889 105 106
 * 106 https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * 先写个递归的把
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC105 implements TreeProblem {
    int[] preorder/*中左右*/;
    int[] inorder/*左中右*/;

    public TreeNode buildTree(int[] preorder/*中左右*/, int[] inorder/*左中右*/) {
        if (preorder.length == 0 || preorder.length != inorder.length) return null;
        this.preorder = preorder;
        this.inorder = inorder;
        return rec(0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode rec(int p1s, int p1e, int p2s, int p2e) {
        TreeNode root = new TreeNode(preorder[p1s]);
        int rootIndex = findA(inorder, preorder[p1s]);
        if (rootIndex == -1) throw new RuntimeException();
        int leftNum = rootIndex - p2s;
        if (rootIndex > p2s) {
            root.left = rec(p1s + 1, p1s + leftNum, p2s, rootIndex - 1);
        }
        if (rootIndex < p2e) {
            root.right = rec(p1s + leftNum + 1, p1e, rootIndex + 1, p2e);
        }
        return root;
    }

    //可用一个hashmap来优化
    //https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/34782/My-recursive-Java-code-with-O(n)-time-and-O(n)-space
    public int findA(int[] arr, int e) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == e) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 6, 5, 8, 12, 14, 4, 7, 11, 9, 13, 10, 15};//preorder/*中左右*/
        int[] b = {6, 3, 2, 12, 14, 8, 5, 1, 11, 7, 13, 9, 4, 15, 10};//inorder/*左中右*/
        TreeNode xx = new LC105().buildTree(a, b);
        System.out.println(xx);
    }
}
